package org.example;

//class RootTree {
//    public static final int JOIN_CONFLICT = 1;
//    public static final int JOIN_CYCLE = 2;
//    public static final int JOIN_SUCCESS = 0;
//
//    private final int[] father;
//
//    RootTree(int n) {
//        father = new int[n + 1];
//        for (int i = 1; i < n + 1; i++) {
//            father[i] = i;
//        }
//    }
//
//    private int find(int u) {
//        if (father[u] == u) {
//            return u;
//        }
//        father[u] = find(father[u]);
//        return father[u];
//    }
//
//    public int tryJoin(int u, int v) {
//        if (v != father[v]) {   //结点最多只能由一个父节点
//            return JOIN_CONFLICT;
//        }
//        u = find(u);
//        if (u == v) {       //有环
//            return JOIN_CYCLE;
//        }
//        father[v] = u;
//        return JOIN_SUCCESS;
//    }
//}
//
////官方题解：https://leetcode.cn/problems/redundant-connection-ii/solutions/416748/rong-yu-lian-jie-ii-by-leetcode-solution/
//class Solution {
//    public int[] findRedundantDirectedConnection(int[][] edges) {
//        int n = edges.length;
//        RootTree rootTree = new RootTree(n);
//        int[] cycle = null;     //记录导致环路的边
//        int[] conflict = null;  //记录导致冲突的边（破坏结点只能有一个父节点的条件）
//        int[] father = new int[n + 1];      //记录结点的直接父节点
//        for (int[] edge : edges) {
//            int joinRet = rootTree.tryJoin(edge[0], edge[1]);
//            if (joinRet != RootTree.JOIN_SUCCESS) {      //当
//                if (joinRet == RootTree.JOIN_CONFLICT) {
//                    conflict = edge;
//                } else {
//                    cycle = edge;
//                }
//                continue;
//            }
//            father[edge[1]] = edge[0];
//        }
//
//        //没有导致冲突的边
//        if (conflict == null) {
//            return cycle;
//        }
//        //有导致冲突的边，也有导致环路的边
//        if (cycle != null) {
//            return new int[]{father[conflict[1]], conflict[1]};
//        }
//        //有导致冲突的边，没有导致环路的边
//        return conflict;
//    }
//}


class UnionFind {
    static int CYCLE = 1;
    static int MULTI_FATHER = 2;
    static int SUCCESS = 0;

    int[] father;
    UnionFind(int n) {
        father = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }

    int find(int u) {
        if (father[u] == u) {
            return u;
        }
        father[u] = find(father[u]);
        return father[u];
    }

    boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    int join(int u, int v) {
        if (find(v) != v) {
            return MULTI_FATHER;
        }
        u = find(u);
        if (u == v) {
            return CYCLE;
        }
        father[v] = u;
        return SUCCESS;
    }
}

//二刷
class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        UnionFind unionFind = new UnionFind(edges.length);
        int[] father = new int[edges.length + 1];
        int[] cycle = null;
        int[] conflict = null;
        for (int[] edge : edges) {
            int ret = unionFind.join(edge[0], edge[1]);
            if (ret != UnionFind.SUCCESS) {
                if (ret == UnionFind.CYCLE) {
                    cycle = edge;
                } else {
                    conflict = edge;
                }
            } else {
                father[edge[1]] = edge[0];
            }
        }
        if (conflict == null) {
            return cycle;
        }
        if (cycle == null) {
            return conflict;
        }
        return new int[]{father[conflict[1]], conflict[1]};
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}